package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 448. 找到所有数组中消失的数字
 * @date 2025/2/17 13:50
 */
public class E448 {

    /**
     * <h3>方法一：计数数组</h3>
     * @param nums 数组
     * @return 缺失的数字
     */
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int[] count = new int[nums.length + 1];
        for(int num : nums) count[num]++;
        for(int i = 1; i < count.length; i++)
            if(count[i] == 0) result.add(i);
        return result;
    }

    /**
     * <h3>方法二：标记数组</h3>
     * @param nums 数组
     * @return 缺失的数字
     */
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        List<Integer> result = new ArrayList<>();
        boolean[] flag = new boolean[nums.length + 1];
        for(int num : nums) flag[num] = true;
        for(int i = 1; i < flag.length; i++)
            if(!flag[i]) result.add(i);
        return result;
    }

    /**
     * <h3>方法三：集合</h3>
     * @param nums 数组
     * @return 缺失的数字
     */
    public List<Integer> findDisappearedNumbers3(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++)
            if (!set.contains(i)) result.add(i);
        return result;
    }

    /**
     * <h3>方法四：惰性求值</h3>
     * @param nums 数组
     * @return 缺失的数字
     */
    public List<Integer> findDisappearedNumbers4(int[] nums) {
        return new java.util.AbstractList<>() {
            private List<Integer> list;
            @Override
            public int size() {
                if (list == null) list = helper(nums);
                return list.size();
            }
            @Override
            public Integer get(int index) {
                if (list == null) list = helper(nums);
                return list.get(index);
            }
        };
    }

    /**
     *
     * @param nums 数组
     * @return 集合
     */
    private List<Integer> helper(int[] nums) {
        List<Integer> result = new ArrayList<>();
        boolean[] flag = new boolean[nums.length + 1];
        for(int num : nums) flag[num] = true;
        for(int i = 1; i < flag.length; i++)
            if(!flag[i]) result.add(i);
        return result;
    }
}
